// 与98类似
// 必须使用中序遍历
// 遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。
class Solution {
 public:
  /*
  TreeNode* pre;
  int Min = INT_MAX;
  int getMinimumDifference(TreeNode* root) {
      func(root);
      return Min;
  }
  void func(TreeNode* root) {
      if(!root) return ;
      func(root->left);
      if(pre&&root->val-pre->val<Min) {
          Min=root->val-pre->val;
      }
      pre=root;
      func(root->right);
  }
  */
  int getMinimumDifference(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    int Min = INT_MAX;
    TreeNode* pre = nullptr;
    while (cur || !st.empty()) {
      if (cur) {
        st.push(cur);
        cur = cur->left;
      } else {
        cur = st.top();
        st.pop();
        if (pre && cur->val - pre->val < Min) Min = cur->val - pre->val;
        pre = cur;

        cur = cur->right;
      }
    }
    return Min;
  }
};